﻿#include "doublearraytrie.h"


const static int gBufSize = 65536 * 32;
const static int gUnitSize = sizeof(int)*2; // size of int + int

DoubleArrayTrie::DoubleArrayTrie() {
    check = new std::vector<int>(gBufSize);
    base = new std::vector<int>(gBufSize);
    used = new std::vector<bool>(gBufSize);
    size = 0;
    allocSize = 0;
    keySize = 0;
    length = nullptr;
    value = nullptr;
    progress = 0;
    nextCheckPos = 0;

    error_ = 0;
}

DoubleArrayTrie::~DoubleArrayTrie() {
    if(check != nullptr) {
        delete check;
        check = nullptr;
    }
    if(base != nullptr) {
        delete base;
        base = nullptr;
    }
    if(used != nullptr) {
        delete used;
        used = nullptr;
    }
    if(length != nullptr) {
        delete length;
        length = nullptr;
    }
    if(value != nullptr) {
        delete value;
        value = nullptr;
    }
}

int DoubleArrayTrie::exactMatchSearch(std::wstring key) {
    return exactMatchSearch(key, 0, 0, 0);
}

int DoubleArrayTrie::exactMatchSearch(std::wstring key, int pos, int len, int nodePos) {
    if (len <= 0)
        len = key.length();
    if (nodePos <= 0)
        nodePos = 0;

    int result = -1;

    const wchar_t * keyChars = key.c_str();

    int b = base->at(nodePos);
    int p;

    for (int i = pos; i < len; i++) {
        p = b + (int)(keyChars[i]) + 1;
        if (b == check->at(p))
            b = base->at(p);
        else
            return result;
    }

    p = b;
    int n = base->at(p);
    if (b == check->at(p) && n < 0) {
        result = -n - 1;
    }
    return result;
}

std::vector<int> DoubleArrayTrie::commonPrefixSearch(std::wstring key) {
    return commonPrefixSearch(key, 0, 0, 0);
}

std::vector<int> DoubleArrayTrie::commonPrefixSearch(std::wstring key, int pos, int len, int nodePos) {
    if (len <= 0)
        len = key.length();
    if (nodePos <= 0)
        nodePos = 0;

    std::vector<int> result;

    const wchar_t * keyChars = key.c_str();

    int b = base->at(nodePos);
    int n = 0;
    int p = 0;

    for (int i = pos; i < len; i++) {
        p = b;
        n = base->at(p);

        if (b == check->at(p) && n < 0) {
            result.push_back(-n - 1);
        }

        p = b + (int)(keyChars[i]) + 1;
        if (b == check->at(p))
            b = base->at(p);
        else
            return result;
    }

    p = b;
    n = base->at(p);

    if (b == check->at(p) && n < 0) {
        result.push_back(-n - 1);
    }

    return result;
}

void DoubleArrayTrie::dump() {
    for (int i = 0; i < size; i++) {
       //qDebug() <<"i: " << i <<" [" << base[i] << ", " << check[i] << "]";
    }
}

int DoubleArrayTrie::resize(int newSize) {
    base->resize(newSize);
    check->resize(newSize);
    used->resize(newSize);
    return allocSize = newSize;
}

int DoubleArrayTrie::fetch(Node parent, std::vector<Node> &siblings) {
    if (error_ < 0)
        return 0;

    int prev = 0;

    for (int i = parent.left; i < parent.right; i++) {
        if ((length != nullptr ? length[i] : key.at(i).length()) < parent.depth)
            continue;

        std::wstring tmp = key.at(i);

        int cur = 0;
        if ((length != nullptr ? length[i] : tmp.length()) != parent.depth)
            cur = (int) tmp.at(parent.depth) + 1;

        if (prev > cur) {
            error_ = -3;
            return 0;
        }

        if (cur != prev || siblings.size() == 0) {
            Node tmp_node ;
            tmp_node.depth = parent.depth + 1;
            tmp_node.code = cur;
            tmp_node.left = i;
            if (siblings.size() != 0) {
                siblings[(siblings.size() - 1)].right = i;
            }
            siblings.push_back(tmp_node);
        }

        prev = cur;
    }

    if (siblings.size() != 0)
        siblings[(siblings.size() - 1)].right = parent.right;

    return siblings.size();
}

int DoubleArrayTrie::insert(std::vector<Node> siblings) {
    if (error_ < 0)
        return 0;
    if(siblings.size() <= 0) {
        return 0;
    }
    int begin = 0;
    int pos = ((siblings[0].code + 1 > nextCheckPos) ? siblings[0].code + 1 : nextCheckPos) - 1;
    int nonzero_num = 0;
    int first = 0;

    if (allocSize <= pos)
        resize(pos + 1);

outer: while (true) {
        pos++;

        if (allocSize <= pos)
            resize(pos + 1);

        if (check->at(pos) != 0) {
            nonzero_num++;
            continue;
        } else if (first == 0) {
            nextCheckPos = pos;
            first = 1;
        }

        begin = pos - siblings[0].code;
        if (allocSize <= (begin + siblings[(siblings.size() - 1)].code)) {
            // progress can be zero
            double l = (1.05 > 1.0 * keySize / (progress + 1)) ? 1.05 : 1.0 * keySize / (progress + 1);
            resize((int) (allocSize * l));
        }

        if (used->at(begin))
            continue;

        for (int i = 1; i < siblings.size(); i++)
            if (check->at(begin + siblings[i].code) != 0)
                //continue outer;
                goto outer;

        break;
    }

    // -- Simple heuristics --
    // if the percentage of non-empty contents in check between the
    // index
    // 'next_check_pos' and 'check' is greater than some constant value
    // (e.g. 0.9),
    // new 'next_check_pos' index is written by 'check'.
    if (1.0 * nonzero_num / (pos - nextCheckPos + 1) >= 0.95)
        nextCheckPos = pos;

    used->at(begin) = true;
    size = (size > begin + siblings[(siblings.size() - 1)].code + 1) ? size : begin + siblings[(siblings.size() - 1)].code + 1;

    for (int i = 0; i < siblings.size(); i++)
        check->at(begin + siblings[i].code) = begin;

    for (int i = 0; i < siblings.size(); i++) {
        std::vector<Node> new_siblings;

        if (fetch(siblings[i], new_siblings) == 0) {
            base->at(begin + siblings[i].code) = (value != nullptr) ? (-value[siblings[i].left] - 1) : (-siblings[i].left - 1);

            if (value != nullptr && (-value[siblings[i].left] - 1) >= 0) {
                error_ = -2;
                return 0;
            }

            progress++;
            // if (progress_func_) (*progress_func_) (progress,
            // keySize);
        } else {
            int h = insert(new_siblings);
            base->at(begin + siblings[i].code) = h;
        }
    }
    return begin;
}

void DoubleArrayTrie::clear() {
    check->clear();
    base->clear();
    used->clear();

    allocSize = 0;
    size = 0;
}

int DoubleArrayTrie::getUnitSize() {
    return gUnitSize;
}

int DoubleArrayTrie::getSize() {
    return size;
}

int DoubleArrayTrie::getTotalSize() {
    return size * gUnitSize;
}

int DoubleArrayTrie::getNonzeroSize() {
    int result = 0;
    for (int i = 0; i < size; i++)
        if (check->at(i) != 0)
            result++;
    return result;
}

int DoubleArrayTrie::build(std::vector<std::wstring> key) {
    return build(key, NULL, NULL, key.size());
}

int DoubleArrayTrie::build(std::vector<std::wstring> _key, int *_length, int *_value, int _keySize) {
    if (_keySize > _key.size() || _key.size() == 0)
        return 0;

    // progress_func_ = progress_func;

    key = _key;
    keySize = _keySize;

    if(length != nullptr) {
        delete length;
        length = nullptr;
    }
    if(value != nullptr) {
        delete value;
        value = nullptr;
    }

    length = _length;
    value = _value;

    progress = 0;

    resize(gBufSize);

    base->at(0) = 1;
    nextCheckPos = 0;

    Node root_node;
    root_node.left = 0;
    root_node.right = keySize;
    root_node.depth = 0;

    std::vector<Node> siblings;
    fetch(root_node, siblings);
    insert(siblings);

    // size += (1 << 8 * 2) + 1; // ???
    // if (size >= allocSize) resize (size);

    if(used != nullptr) {
        delete used;
        used = nullptr;
    }
    key.clear();
    return error_;
}

